#pragma once

#include "UnionFind.hpp"
#include <limits.h>
#include <queue>

// 默认无向图
template <typename T, typename W, W w_max = INT_MAX, bool Direction = false>
class Graph
{
    typedef UnionFind::UnionFind<T> uf;
    typedef Graph<T, W, w_max, Direction> Self;

    struct Edge
    {
        int _src;
        int _des;
        W _weight;

        Edge(int src, int des, int weight)
            : _src(src), _des(des), _weight(weight)
        {}

        bool operator>(Edge& other)
        {
            return _weight > other._weight;
        }
    };

public:
    Graph(std::vector<T>& vertexs, int n)
    {
        _vertex.reserve(n);
        for (int i = 0; i < n; i++)
        {
            _hash[_vertex[i]] = i; 
            _vertex.push_back(vertexs[i]);
        }
        _matrix.resize(n);
        for (int i = 0; i < n; i++)
        {
            _matrix[i].resize(n, w_max);
        }
    }

    // 获取顶点下标
    int GetVertexIndex(T &e)
    {
        auto it = _hash.find(e);
        if (it != _hash.end())
        {
            return it->second;
        }
        else
        {
            throw invalid_argument("顶点不存在");
            return -1;
        }
    }

    // 添加一条边
    bool AddEdge(T src, T des, int weight)
    {
        int src_idx = _hash[src], des_idx = _hash[des];
        if (_matrix[src_idx][des_idx] != w_max)
            return false;
        _matrix[src_idx][des_idx] = weight;
        // 如果是无向图
        if (Direction == false)
        {
            _matrix[des_idx][src_idx] = weight;
        }
        return true;
    }

    void Print()
    {
        // 顶点
        for (size_t i = 0; i < _matrix.size(); i++)
        {
            std::cout << "[" << i << "]" << "->" << _vertex[i] << std::endl;
        }
        std::cout << std::endl;
        // 矩阵
        //  std::cout << "  ";
        for (size_t i = 0; i < _matrix.size(); i++)
        {
            for (size_t j = 0; j < _matrix.size(); j++)
            {
                if (i == j)
                    printf("%-4d", 0);
                else if (_matrix[i][j] == w_max)
                {
                    printf("%s   ", "∞");
                }
                else
                {
                    printf("%-4d", _matrix[i][j]);
                }
            }
            std::cout << std::endl;
        }
    }

    // BFS层序遍历所有边
    // 并判断是否有环
    void BFS(const T &org)
    {
        int idx = _hash[org];
        int n = _matrix.size();
        std::vector<bool> vis(n);
        std::queue<int> q;
        q.push(idx);
        vis[idx] = true;
        while (!q.empty())
        {
            int size = q.size();
            while (size--)
            {
                auto e = q.front();
                q.pop();
                idx = e;
                std::cout << idx << ":" << "[" << _vertex[idx] << "]" << " ";
                for (int j = 0; j < n; j++)
                {
                    if (!vis[j] && _matrix[idx][j] != w_max)
                    {
                        q.push(j);
                        vis[j] = true;
                    }
                }
            }
        }
        // 检查看是否有孤岛，如果有，就对孤岛也遍历一遍
        for (int i = 0; i < n; i++)
        {
            if (!vis[i])
            {
                q.push(i);
                vis[i] = true;
                while (!q.empty())
                {
                    int size = q.size();
                    while (size--)
                    {
                        auto e = q.front();
                        q.pop();
                        idx = e;
                        std::cout << idx << " : " << "[" << _vertex[idx] << "]" << " ";
                        for (int j = 0; j < n; j++)
                        {
                            if (!vis[j] && _matrix[idx][j] != w_max)
                            {
                                q.push(j);
                                vis[j] = true;
                            }
                        }
                    }
                }
            }
        }
        std::cout << std::endl;
    }

    void DFS(const T& src)
    {
        int idx = _hash[src];
        int n = _matrix.size();
        std::vector<bool> vis(n);
        _DFS(idx, vis, n);
        //检查孤岛
        std::cout << std::endl;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i])
            {
                _DFS(i, vis, n);
            }
        }
    }

    //寻找最小生成树，适用于无向图
    //总共n个顶点，找到只需要n-1边
    //贪心策略：每次全局的寻找一条权最小的边，要判环
    W Kruskal(Self& minTree)
    {
        int n = _matrix.size();
        minTree._matrix.resize(n);
        for (int i = 0; i < n; i++)
        {

        }
        int n = _matrix.size();
        //把所有的边加入优先级队列, 建小堆
        std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
        _uf
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
            {
                if (_matrix[i][j] != w_max)
                    pq.push(Edge(i, j, _matrix[i][j]));
            }
        W totalw = W();
        int size = 0;
        while (!pq.empty())
        {
            Edge e = pq.top();
            pq.pop();
            //如果该边的两个顶点已经在同一颗树中，再添加就会成环，因此不能添加
            if (!_uf.InSameSet(_vertex[e._src], _vertex[e._des]))
            {
                std::cout << _vertexs[e._srci] << "->" << _vertexs[e._dsti] <<":" << e._w << std::endl;
                _uf.UnionSet(_vertex[e._src], _vertex[e._src]);
                totalw += e._weight;
                size++
            }
            else
            {
                std::cout << "构成环: ";
                std::cout << _vertexs[e._srci] << "->" << _vertexs[e._dsti] << ":" << e._w << std::endl;
            }
            if (size == n - 1)
            {
                break;
            }
        }
        if (size == n - 1)
            return totalw;
        return W();
    }

private:
    void _DFS(int srci, std::vector<bool>& vis, int n)
    {
        std::cout << srci << ":" << "[" << _uf.FindValue(srci) << "]" << " ";
        vis[srci] = true;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && _matrix[srci][i] != w_max)
            {
                _DFS(i, vis, n);
            }
        }
    }

private:
    uf _uf;
    std::vector<int> _vertex;
    std::map<T, int> _hash;                            // 并查集
    std::vector<std::vector<W>> _matrix; // 邻接矩阵
};

void TestGraph1()
{
    std::vector<char> c;
    c.push_back('0');
    c.push_back('1');
    c.push_back('3');
    c.push_back('2');
    Graph<char, int, INT_MAX, true> g(c, 4);
    g.AddEdge('0', '1', 1);
    g.AddEdge('0', '3', 4);
    g.AddEdge('1', '3', 2);
    g.AddEdge('1', '2', 9);
    g.AddEdge('2', '3', 8);
    g.AddEdge('2', '1', 5);
    g.AddEdge('2', '0', 3);
    g.AddEdge('3', '2', 6);
    // g.Print();
    g.BFS('0');
    g.DFS('0');
    g.Print();
}
